package com.snopy.graph;

import java.util.*;

/**
 * @author snopy
 * @version 1.0.0
 * @classname GraphDemo
 * @description arc
 * @email 77912204@qq.com
 * @date 2022/11/03 11:07
 */
public class GraphDemo {
    //abcd
    //
    static final int SEG_COUNT = 4;
    static List<String> list = new ArrayList<>();
    static int[] segments = new int[SEG_COUNT];
    public static void main(String[] args) {
        int[] nums = new int[]{2,1,0,2};
        int target = largestRectangleArea(nums);
        System.out.println(target);
    }
    public int shortestPathAllKeys(String[] grid) {
        String [][] grids = new String[grid.length][grid[0].length()];

        return 0;
    }



    public static int largestRectangleArea(int[] heights) {
        if(heights == null){
            return 0;
        }
        if (heights.length == 1){
            return heights[0];
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;

        for(int i = 0; i < heights.length; i++){
            int w = 1;
            int t = heights[i];
            boolean lflag = true,rflag = true;
            int l = i-1,r = i + 1;
            while(lflag || rflag){
                if( l >=0 && heights[l--] >= t && lflag){
                    w++;
                }else{
                    lflag = false;
                }
                if( r < heights.length && heights[r++] >= t && rflag){
                    w++;
                }else{
                    rflag = false;
                }
            }
            max = Math.max(max,w * t);
        }
        return max;
    }

    public static List<String> restoreIpAddresses(String s) {

        dfs(s,0,0);
        return list;
    }
    public static void dfs(String s,int segId,int segStart){
        //如果遍历到了第4
        if (segId == SEG_COUNT){
            if (segStart == s.length()){
                StringBuilder ipAddr = new StringBuilder();
                for (int i = 0 ; i < SEG_COUNT; i++){
                    ipAddr.append(segments[i]);
                    if (i != SEG_COUNT - 1){
                        ipAddr.append('.');
                    }
                }
                list.add(ipAddr.toString());
            }
            return;
        }
        if (segStart == s.length()){
            return;
        }
        if (s.charAt(segStart) == '0'){
            segments[segId] = 0;
            dfs(s,segId + 1,segStart + 1);
        }

        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); segEnd++){
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 255){
                segments[segId] = addr;
                dfs(s,segId + 1,segEnd + 1);
            }else {
                break;
            }
        }

    }
    public static int compareVersion(String version1, String version2) {
        String [] v1arr = version1.split("\\.");
        String [] v2arr = version2.split("\\.");
        int len = Math.max(v1arr.length,v2arr.length);
        int v1 = 0,v2 = 0;
        for (int i = 0; i < len; i++){
            v1 = (v1arr.length > i ? Integer.parseInt(v1arr[i]) : 0);
            v2 = (v2arr.length > i ? Integer.parseInt(v2arr[i]) : 0);
            if (v1 > v2){
                return 1;
            }
            if (v1 < v2){
                return -1;
            }
        }
        return 0;
    }
    public String shortestPalindrome(String s) {
        int[] arr = new int[s.length()];
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            int pre = i,last = i;

        }
        return "";
    }
}
